package 题目集.hash.字符串哈希;

import org.junit.Test;

//https://leetcode.cn/problems/repeated-string-match/description/
public class 重复叠加字符串匹配 {
    /**
     * 暴力解：
     *      找到a中第一个与b开头匹配的点，然后从这个点开始，逐个比较a和b的字符是否相等。
     *      如果a长度不够则拼接a，直到b的所有字符都匹配完，或者a中所有匹配b开头的点都不能拼出b。
     *      时间复杂度：O(n*m)
     *  优化：
     *      首先：将a拼接到长度一定能够包含b的长度，然后再进行字符串匹配（可以KMP，也可以字符串哈希）。
     *      一定能够包含b的长度：(b.length()) / a.length() 向上取整+ 1
     */
    static long P = 31; //进制，这里采用31是为了避免和字符串中的字符冲突
    static long[] base; //存储P的幂次
    static long[] hashA; //存储字符串的哈希值
    static char[] charA; //存储字符串的字符
    static char[] charB; //存储字符串的字符
    static int an; //a的长度
    static int bn; //b的长度

    public int repeatedStringMatch(String a, String b) {
        charA = a.toCharArray();
        charB = b.toCharArray();
        an = charA.length;
        bn = charB.length;
        initHash();
        long hashB = getHash(charB, charB.length);    //计算b的哈希值
        for (int i = 1; i < hashA.length - bn; i++) {
            if (hash(i, i + bn - 1) == hashB) {
                return (i + bn - 1) / an + ((i + bn - 1) % an == 0 ? 0 : 1);
            }
        }
        return -1;
    }

    public static void initHash() {
        int n = (bn + an - 1) / an + 1;     //最多要拼接的次数。(bn+an-1) / an 为向上取整
        int len = an * n;       //拼接后的字符串长度
        hashA = new long[len + 1];
        base = new long[len + 1];
        base[0] = 1;
        for (int i = 1; i <= len; i++) {
            base[i] = base[i - 1] * P;
        }
        int cnt = 1;
        for (int i = 0; i < n; i++) {   //拼接n次，并计算每次每个前缀的哈希值
            for (int j = 0; j < an; j++) {
                hashA[cnt] = hashA[cnt - 1] * P + (charA[j] - 96);  //进一位再加上当前字符
                cnt++;
            }
        }
    }

    /**
     * 计算字符串0-n的哈希值
     */
    public static long getHash(char[] chars, int n) {
        long res = 0;
        for (int i = 0; i < n; i++) {
            res = res * P + (chars[i] - 96);
        }
        return res;
    }

    public static long hash(int l, int r) {
        return hashA[r] - hashA[l - 1] * base[r - l + 1];
    }

    @Test
    public void test() {
        System.out.println(repeatedStringMatch("ababab", "cdabcdab"));
    }
}
